/**
 * //给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * //
 * //
 * //
 * // 示例 1：
 * //
 * //
 * //
 * //
 * //输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * //输出：6
 * //解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 * //
 * //
 * // 示例 2：
 * //
 * //
 * //输入：height = [4,2,0,3,2,5]
 * //输出：9
 * //
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // n == height.length
 * // 1 <= n <= 2 * 10⁴
 * // 0 <= height[i] <= 10⁵
 * //
 * //
 * // Related Topics 栈 数组 双指针 动态规划 单调栈 👍 3832 👎 0
 */

package com.xixi.basicAlgroithms.dynamicPrograming;

public class ID00042TrappingRainWater {
    public static void main(String[] args) {
        Solution solution = new ID00042TrappingRainWater().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int trap(int[] height) {
            int n = height.length;
            int res = 0;
            if (n <= 1) return res;

            //定义两个指针，从左右两边接水
            int left = 0;
            int right = n - 1;
            //记录左指针左边的的max
            int leftLeftMax = 0;
            //记录右指针右边的max
            int rightRightMax = 0;


            while (left < right) {
                //用左指针更新左边的max
                leftLeftMax = Math.max(height[left], leftLeftMax);
                //用右指针更新右边的max
                rightRightMax = Math.max(height[right], rightRightMax);

                //说明leftLeftMax < rightRightMax < leftRightMax
                if (height[left] < height[right]) {
                    //如果height[left] == leftLeftMax，就没法接水，所以0位不用担心
                    res += leftLeftMax - height[left];
                    //左指针右移
                    ++left;
                } else {//height[left] >= height[right]
                    //说明rightLeftMax >= leftLeftMax >= rightRightMax
                    res += rightRightMax - height[right];
                    --right;
                }


            }


            return res;

        }
    }


//leetcode submit region end(Prohibit modification and deletion)


    //动态规划
    public int trapDynamic(int[] height) {
        int n = height.length;
        int res = 0;
        if (n <= 1) return res;

        //不包含i的左右边最高墙
        int[] max_left = new int[n];
        int[] max_right = new int[n];
        int i = 1;
        int maxLeftNow = height[0]; //初始化max_left[1]左边最高为height[0]
        for (; i < n; i++) {
            max_left[i] = maxLeftNow;
            maxLeftNow = Math.max(maxLeftNow, height[i]);
        }
        i = n - 2;
        int maxRightNow = height[n - 1]; //初始化

        for (; i >= 0; i--) {
            max_right[i] = maxRightNow;
            maxRightNow = Math.max(maxRightNow, height[i]);
        }

        //开始求每一列的雨水
        i = 1;
        for (; i < n - 1; i++) {
            int minWall = Math.min(max_left[i], max_right[i]);
            if (minWall > height[i]) {
                res += (minWall - height[i]);
            }
        }



        return res;

    }

}